//爬楼梯

//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
//注意：给定 n 是一个正整数。

//     示例 1：                              示例 2：
//     输入： 2                              输入： 3
//     输出： 2                              输出： 3
//     解释： 有两种方法可以爬到楼顶。       解释： 有三种方法可以爬到楼顶
//            1 阶 + 1 阶                           1 阶 + 1 阶 + 1 阶
//            2 阶                                  1 阶 + 2 阶
//                                                  2 阶 + 1 阶

//思路:
//爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
//那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。
//所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。
//我们来分析一下，动规五部曲：
//定义一个一维数组来记录不同楼层的状态：确定dp数组以及下标的含义。dp[i]： 爬到第i层楼梯，有dp[i]种方法
//
//（1）确定递推公式
//从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。
//首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。dp[i-1]的所有方法都跳一步，那还是dp[i-1]种方法
//还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。dp[i-2]的所有方法都跳两步，那还是dp[i-2]种方法
//那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！所以 dp[i] = dp[i - 1] + dp[i - 2] 。
//在推导dp[i]的时候，一定要时刻想着dp[i]的定义，否则容易跑偏。
//（2）dp数组如何初始化。在回顾一下dp[i]的定义：爬到第i层楼梯，有dp[i]中方法。
//所以我的原则是：不考虑dp[0]如果初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。
//（3）确定遍历顺序：从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的

class Solution      
{
public:
    int climbSrairs(int n)
    {
        if(n <= 1)  return n; //dp[i-2]
        vector<int> dp(n+1);
        dp[1] = 1;
        dp[2] = 2;

        for(int i = 3; i <= n; ++i) //从前往后遍历
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};
//时间复杂度O(n)，空间复杂度O(n)

//优化
class Solution      
{
public:
    int climbSrairs(int n)
    {
        if(n <= 1)  return n; //dp[i-2]
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;

        for(int i = 3; i <= n; ++i) //从前往后遍历
        {
            int sum = dp[1] + dp[2]; //用一个中间变量来保存两个的和
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2]; //返回的是sum，dp[2]=sum，即dp[2]
    }
};
//时间复杂度O(n)，空间复杂度O(1)
